package 面试常见刷题;


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class 树的遍历 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.right = new TreeNode(3);
        System.out.println(preorderTraversal(root));
        System.out.println(inorderTraversal(root));
        System.out.println(postorderTraversal(root));
    }

    // 前序遍历
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            ans.add(pop.value);
            if (pop.right != null) stack.push(pop.right);
            if (pop.left != null) stack.push(pop.left);
        }
        return ans;
    }

    // 中序遍历
    public static List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        if(root ==null) return ans;
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode now = root;
        while (!stack.isEmpty()|| now!=null){
            if(now!=null){
                stack.push(now);
                now = now.left;
            }else{
                now = stack.pop();
                ans.add(now.value);
                now = now.right;
            }
        }
        return ans;
    }

    // 后序遍历
    public static List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        ArrayDeque<Integer> out = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            out.push(pop.value);
            if (pop.left != null) stack.push(pop.left);
            if (pop.right != null) stack.push(pop.right);
        }
        while (!out.isEmpty()) {
            ans.add(out.pop());
        }
        return ans;
    }
}
